1. Field of the Invention
This invention relates generally to a program compiler optimization method and particularly to a technique for generating efficient object code for intrinsic Fortran 90 array variable transformation functions.
2. Description of the Related Art
Recently, the X3J3 subcommittee of the American and National Standards Institute (ANSI), in collaboration with a corresponding International Standards Organization (ISO) group ISO/IEC JTC1/SC22/WG5, approved a new standard for the Fortran programming language. This new Fortran programming language standard is generally denominated the "Fortran 90" language standard and is also in the art denominated the "Fortran 90 Array" language standard. While maintaining compatibility with and providing support for the previous "FORTRAN 77" language standard, this new Fortran 90 Array language standard defines many new programming constructs and functions.
Among these new features are the "array language" protocols. Fortran programs in the Fortran 90 language may specify operations to be performed on entire arrays or on specific sections of arrays. To facilitate these new array operations, the Fortran 90 standard defines a new class of intrinsic array functions denominated "transformational functions". The Fortran 90 standard is promulgated by the ISO as the International Fortran Standard specification number ISO/IEC 1539:1991 and is promulgated by the ANSI as specification number ANSI X3.198-199x.
The new features promulgated in the Fortran 90 language standard create new challenges for existing Fortran compiler and preprocessor technology. The existing FORTRAN 77 compilers do not address the array transformational functions and must be completely rewritten and restructured to accommodate the Fortran 90 standard. The new problems created by Fortran 90 array constructs can be appreciated with reference to the FORTRAN compiler art.
FIG. 1 illustrates a procedure for translating a FORTRAN program 10 to create an executable binary object program 12. A lexical/syntax analysis 14 is conducted to transform source program 10 to a first intermediate language program 16. First intermediate language program 16 is then processed by an optimization routine 18 to create a second intermediate language program 20, which is then directly interpreted by the code generation routine 22 to create object program 12.
Lexical/syntax analysis routine 14 and code generation routine 22 are easily defined in terms of the Fortran 90 specification and the machine binary code set, respectively. Thus, it is optimization routine 18 that is primarily affected by the new Fortran 90 standard. Optimization routine 18 is illustrated in FIG. 2 as it is understood in the art. Optimization processing is achieved by first performing a control flow analysis in routine 24 of first intermediate language 16. Control flow analysis routine 24 provides the control flow data 26, which are then passed to a data-flow analysis routine 28 wherein first intermediate language program 16 is analyzed for data flow. Data-flow analysis routine 28 produces the data-flow data 30. Finally, a program transformation procedure 32 accepts control flow data 26, data-flow data 30 and first intermediate language program 16 to produce second intermediate language program 20.
Many methods for analyzing relationships between definitions and uses of variables and arrays are known in the art. For instance, in U.S. Pat. No. 4,773,007, Yasusi Kanada et al. disclose a program translation method for obtaining appropriate array definition and use relationships in a DO-loop that contains a conditional statement or control structure. Kanada et al. teach a process where data flow analysis procedure 28 checks for the presence of intra-loop changes to array variables before passing control to program transformation procedure 32. In their method, program transformation procedure 32 is executed only if the array definition/use relationship data indicate that the elements of an array variable will be rewritten within a loop. Kanada et al. suggest comparing subscripts associated with the array definition and the array use to test this indication.
In U.S. Pat. No. 4,833,606, Kyoko Iwasawa et al. disclose a compiling method for vectorizing multiple DO-loops. Their method detects variables that are defined in one loop and referenced by another and maps the variable information into a dependency graph that is used to analyze data dependencies of each loop level. Iwasawa et al. disclose a compiler procedure that inserts control statements to assure preservation of initial and end values for the loops, thereby minimizing the size of the working (temporary) arrays. The object of this method is to make it possible to perform vector operations for an outer loop by transforming variables into arrays, permitting the variables having values defined in the outer loop to be used in the inner loop and also permitting these variables with values defined in the inner loop to be replaced by the arrays so that the vectorization process can be performed for the outer loop. Iwasawa et al. teach a method for detecting connected components linked together by an arc in a data dependency graph indicative of the sequence of definitions and use of variables in multiple loops.
Similarly, in U.S. Pat. No. 5,109,331, Kazuhisa Ishida et al. disclose a method for source program compilation by analyzing a subscript in an array variable included in a loop. They optimize program execution by employing an "induction variable" represented by a standard form expressed by an initial value in a first loop iteration and an increment value for each subsequent loop iteration. A subscript in a loop array is represented by linear coupling to the standard form. Subscript independency and dependency within the loop is tested during compilation. Basically, Ishida et al. search for identical array elements having different names and force them to the identical storage location in the executable binary code, thereby saving memory and processing steps.
Thus, practitioners in the art generally employ "subscript tables" during compilation of array variables. A subscript table is a data structure commonly employed in the optimization process 18 (FIG. 1 ) and consists of a two-dimensional array containing elements of type integer and pointers to expressions that collectively encode all of the information pertaining to the sub script expressions and their enclosing DO- loops. Practitioners in the compiler art have developed formal "dependency-analysis" procedures using constructs such as subscript tables to decompose nested DO-loops into parallel strings suitable for simultaneous execution in multi-processor arrays.
For instance, Zhiyuan Li et al. ("Program Parallelization with Interprocedural Analysis", The Journal of Supercomputing, vol. 2, pp 225-44, Kluwer Academic Publishers, Boston, Mass., 1988) provide a useful general discussion of interprocedural analysis for parallel computing that introduces several useful formal concepts related to the use of sub script tables in dependency analysis. Li et al. examine several methods for interprocedural data dependency analysis, including "atom images". The atom images method is useful for resolving cases of difficult and inefficient data dependency.
Also, E. D. Kyriakis-Bitzaros et al. ("An Efficient Decomposition Technique for Mapping Nested Loops with Constant Dependencies into Regular Processor Arrays", Journal of Parallel and Distributed Computing, vol. 16, pp. 258-264, Academic Press, Inc., 1992) discuss a method for mapping nested loops with constant dependencies into distributed memory multiprocessors. Kyriakis-Bitzaros et al. discuss "loop index space", which is a concept used in compiler optimization that leads to improved binary code efficiency. They introduce the "Augmented Dependence Graph" (ADG) as a device for separating different variables having equal indices in multiple nested loop statements.
Despite extensive effort in the compiler art related to array variable and nested DO-loop optimization, the array transformation functions introduced by the new Fortran 90 standard bring with them new inefficiencies in storage and processing and there is an accordingly clearly-felt need in the art for more efficient compiling procedures suitable for application to these new intrinsic Fortran 90 array transformation functions.
This problem can be better understood by considering an example. The Fortran 90 standard specification of the SPREAD function is provided in TABLE 1 below and the Fortran 90 specification of the TRANSPOSE function is provided in TABLE 2 below.
TABLE I __________________________________________________________________________ 13.13.101 SPREAD (SOURCE, DIM, NCOPIES) __________________________________________________________________________ Description. Replicates an array by adding a dimension. Broadcasts several copies of SOURCE along a specified dimension (as in forming a book from copies of a single page) and thus forms an array of rank one greater. Class. Transformational function. Arguments. SOURCE may be of any type. It may be scalar or array valuesd. The rank of SOURCE must be less than 7. DIM must be scalar and of type integer with value in the range 1 .ltoreq. DIM ' n + 1, where n is the rank of SOURCE. NCOPIES must be scalar and of type integer. Result Type, Type Parameter, and Shape. The result is an array of the same type and type parameters as SOURCE and of rank n + 1, where n is the rank of SOURCE. Case (i): If SOURCE is scalar, the shape of the result is (MAX, (NCOPIES, 0)). Case (ii): If SOURCE is array valued with shape (d.sub.1, d.sub.2, . . ., d.sub.n), the shape is (d.sub.1, d.sub.2, . . ., d.sub.DIM-1, MAX (NCOPIES, 0), d.sub.DIM, . . ., d.sub.n). Result Value. Case (i): If SOURCE is scalar, each element of the result has a value equal to SOURCE. Case (ii): If SOURCE is array valued, the element of the result with subscripts (r.sub.1, r.sub.2, . . ., r.sub.n+1) has the value source (r.sub.1, r.sub.2, . . ., r.sub.DIM-1, r.sub.DIM+1, . . ., r.sub.n+1). ##STR1## if NC has the value 3 and is a zero-sized array of NC has the value __________________________________________________________________________ 0.
TABLE 2 __________________________________________________________________________ 13.13.109 TRANSPOSE (MATRIX) __________________________________________________________________________ Description. Transpose an array of rank two. Class. Transformational function. Argument. MATRIX may be of any type and must have rank two. Result type, Type Parameters, and Shape. The result is an array of the same type and type parameters as MATRIX and with rank two and shape (n, m) where (m, n) is the shape of MATRIX. Result Value. Element (i, j) of the result has the value MATRIX (j, i) = 1, 2, . . ., n; j = 1, 2, . . ., m. ##STR2## __________________________________________________________________________
Consider the following exemplary Fortran 90 program. ##EQU1##
Examination of the semantics of the SPREAD function in TABLE 1 suggest the Fortran 90 program translation provided below in TABLE 3.
TABLE 3 ______________________________________ REAL A(100, 100), B(100), C(100, 100, 100) integer new.sub.-- loop.sub.-- 1 integer new.sub.-- loop.sub.-- 2 integer new.sub.-- loop.sub.-- 3 real temporary.sub.-- array.sub.-- 1(100, 100, 100) real temporary.sub.-- array.sub.-- 2(100, 100) real temporary.sub.-- array.sub.-- 3(100, 100, 100) do new.sub.-- loop.sub.-- 3 = 1,100 do new.sub.-- loop.sub.-- 2 = 1,100 do new.sub.-- loop.sub.-- 1 = 1,100 temporary.sub.-- array.sub.-- 1 (new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 2, new.sub.-- loop.sub.- - 3) = * A(new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 3) enddo enddo enddo do new.sub.-- loop.sub.-- 2 = 1,100 do new.sub.-- loop.sub.-- 1 = 1,100 temporary.sub.-- array.sub.-- 2 (new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 2) = B(new.sub. -- loop.sub.-- 1) enddo enddo do new.sub.-- loop.sub.-- 3 = 1,100 do new.sub.-- loop.sub.-- 2 = 1,100 do new.sub.-- loop.sub.-- 1 = 1,100 temporary.sub.-- array.sub.-- 3 (new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 2, new.sub.-- loop.sub.- - 3) = * temporary.sub.-- array.sub.-- 2(new.sub.-- loop.sub.-- 2, new.sub.-- loop.sub.-- 3) enddo enddo enddo do new.sub.-- loop.sub.-- 3 = 1,100 do new.sub.-- loop.sub.-- 2 = 1,100 do new.sub.-- loop.sub.-- 1 = 1,100 C(new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 2, new.sub.-- loop.sub. -- 3) = * temporary.sub.-- array.sub.-- 1 (new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 2, new.sub.-- loop.sub.-- 3) + * temporary.sub. -- array.sub.-- 3 (new.sub.-- loop.sub.-- 1, new.sub.-- loop.sub.-- 2, new.sub.-- loop.sub.-- 3) enddo enddo enddo END ______________________________________
The intermediate program in TABLE 3 contains a total of 11 DO-loops herein denominated "scalarized loops". Note that three temporary arrays, occupying 2,010,000 storage elements, are created by the scalarizing translation process. The translation approach leading to the program in TABLE 3, although easy for the Scalarizer component of a compiler or preprocessor, is intolerably efficient at execution time in both storage space and execution steps. Nevertheless, this approach is the only translation approach known in the art for the new SPREAD function introduced by the Fortran 90 standard. Similar problems are known for the usual translation procedures applied to the TRANSPOSE function shown above in TABLE 2 as well as the CSHIFT function specified below in TABLE 4 and the EOSHIFT function specified below in TABLE 5.
TABLE 4 __________________________________________________________________________ 13.13.25 CSHIFT (ARRAY, SHIFT, DIM) __________________________________________________________________________ Optional Argument. DIM Description. Perform a circular shift on an array expression of rank one or perform circular shifts on all the complete rank one sections along a given dimension of an array expression of rank two or greater. Elements shifted out at one end of a section are shifted in at the other end. Different sections may be shifted by different amounts and in different directions. Class. Transformational function. Arguments. ARRAY may be of any type. It must not be scalar. SHIFT must be of type integer and must be scalar if ARRAY has rank one; otherwise, it must be scalar or of rank n - 1 and of shape (d.sub.1, d.sub.2, . . ., d.sub.DIM-1, d.sub.DIM+1, . . ., d.sub.n) where (d.sub.1, d.sub.2, . . ., d.sub.n) is the shape of ARRAY. DIM must be a scalar and of type integer with a value in the range (optional) 1 .ltoreq. DIM .ltoreq. n, where n is the rank of ARRAY. If DIM is omitted, it is as if it were present with the value 1. Result Type, Type parameter, and Shape. The result is of the type and type parameters of ARRAY, and has the shape of ARRAY. Result Value. Case (i): If ARRAY has rank one, element i of the result is ARRAY (1 + MODULO (i +SHIFT - 1, SIZE (ARRAY))). Case (ii): If ARRAY has rank greater than one, section (s.sub.1, s.sub.2, . . ., s.sub.DIM-1, :, S.sub.DIM+1, . . ., s.sub.n) of the result has a value equal to CSHIFT (ARRAY (s.sub.1, s.sub.2, . . ., s.sub.DIM-1, :, s.sub.DIM+1, . . ., s.sub.n), 1, sh), where sh is SHIFT or SHIFT (s.sub.1, s.sub.2, . . ., s.sub.DIM-1, s.sub.DIM+1, . . ., s.sub.n). Examples. Case (i): If V is the array [1, 2, 3, 4, 5, 6], the effect of shifting V circularly to the left by two positions is achieved by CSHIFT (V, SHIFT = 2) which has the value [3, 4, 5, 6, 1, 2]; CSHIFT (V, SHIFT = -2) achieves a circular shift to the right by two positions and has the value (5, 6, 1, 2, 3, 4]. Case (ii): The rows of an array of rank two may all be shifted by the same amount or by ##STR3## ##STR4## ##STR5## __________________________________________________________________________
TABLE 5 __________________________________________________________________________ 13.13.32 EOSHIFT (ARRAY, SHIFT, BOUNDARY, DIM) __________________________________________________________________________ Optional Argument. BOUNDARY, DIM Description. Perform an end-off shift on an array expression of rank one or perform end-off shifts on all the complete rank-one sections along a given dimensions of an array expression of rank two or greater. Elements are shifted off at one end of a sections and copies of a boundary value are shifted in at the other end. Different sections may have different boundary values and may be shifted by different amounts and in different directions. Class. Transformational function. Arguments. ARRAY may be of any type. It must not ne scalar. SHIFT must be of type integer and must be scalar if ARRAY has rank one; otherwise, it must be scalar or fo rank n - 1 and of shape (d.sub.1, d.sub.2, . . ., d.sub.DIM-1, d.sub.DIM+1, . . ., d.sub.n) where (d.sub.1, d.sub.2, . . ., d.sub.n) is the shape of ARRAY. BOUND- ARY (optional) must be of the same type and type parameters as ARRAY and must be scalar if ARRAY has rank one; otherwise it must be either scalar or of rank n - 1 and of shape (d.sub.1, d.sub.2, . . ., d.sub.DIM-1, d.sub.DIM+1, . . ., d.sub.n). BOUNDARY may be omitted for the data types in the following table end, in this case, it is as if it were present with the scalar value shown. __________________________________________________________________________ Type of ARRAY Value of BOUNDARY __________________________________________________________________________ Integer 0 Real 0.0 Complex (0.0, 0.0) Logical false Character (len) len blanks __________________________________________________________________________ DIM (optional) must be scalar and of type integer with a value in the range .ltoreq. DIM .ltoreq. n, where n is the rank of ARRAY. If DIM is omitted, it is as if it were present with the value Result Type, Type Parameter, and Shape. The result has the type, type parameters, and shape of ARRAY. Result Value. Element (s.sub.1, s.sub.2, . . ., s.sub.n) of the result has the value ARRAY (s.sub.1, s.sub.2, . . ., s.sub.n) of the result has the value ARRAY (s.sub.1, s.sub.2, . . ., s.sub.DIM-1, s.sub.DIM + sh, s.sub.DIM+1, . . ., s.sub.n) where sh is SHIFT or SHIFT (s.sub.1, s.sub.2, . . ., s.sub.DIM-1, s.sub.DIM+1, . . ., s.sub.n) provided the inequality LBOUND (ARRAY, DIM) .ltoreq. s.sub.DIM + sh .ltoreq. UBOUND (ARRAY, DIM) holds and is otherwise BOUNDARY or BOUNDARY (s.sub.1, s.sub.2, . . ., s.sub.DIM-1, s.sub.DIM+1, . . ., s.sub.n). Examples. Case (i): If V is the array [1, 2, 3, 4, 5, 6], the effect of shifting V end-off to the left by 3 positions is achieved by EOSHIFT (V, SHIFT = 3) which has the value [4, 5, 6, 0, 0, 0]; EOSHIFT (V, SHIFT = -2, boundary = 99) achieves and end-off shift to the right by 2 positions with the boundary value of 99 and has the value [99, 9, 1, 2, 3, 4]. Case (ii): The rows of an array of rank two may all be shifted by the same amount or by different amounts and the boundary elements can be the same or different. If M ##STR6## ##STR7## ##STR8## __________________________________________________________________________
The millions of steps and millions of temporary storage elements required for the relatively simple application of the Fortran 90 SPREAD function discussed above in connection with TABLE 3 suggest that there is a clearly-felt need in the art for improved optimization procedures for the intrinsic Fortran 90 array transformational functions. The related unresolved problems and deficiencies are clearly felt in the art and are solved by this invention in the manner described below.